package C060;

/**
 * ClassName: c04
 * Package: C060
 * Description: https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting/description/ 2127. 参加会议的最多员工数
 *
 *
 *
 n == favorite.length
 2 <= n <= 105
 0 <= favorite[i] <= n - 1
 favorite[i] != i
 一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
 员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
 给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。
 * @Author BCXJ
 * @Create 2025/11/28 22:11
 * @Version 1.0
 * @Since 1.0
 */
public class c04 {
    public static void main(String[] args) {
        int[] arr = {1,0,3,2,5,6,7,4,9,8,11,10,11,12,10};
        System.out.println(maximumInvitations(arr));
    }

    // index -> fav[index]
    public static int maximumInvitations(int[] favorite) {
        int n = favorite.length;
        // 1.1 统计入度
        int[] indegree = new int[n];
        for (int i = 0; i < favorite.length; i++) {
            indegree[favorite[i]]++;
        }
        // 1.2 入度为0 入队列
        int[] queue = new int[n];
        int l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            if(indegree[i] == 0) {
                queue[r ++] = i;
            }
        }

        // 统计深度
        int[] deep = new int[n];
        while(l < r) {
            int cur = queue[l++];
            int next = favorite[cur];
            // 这个节点的指向的节点 深度需要 + 1
            deep[next] = Math.max(deep[next], deep[cur] + 1);
            if(-- indegree[next] == 0) {
                queue[r ++] = next;
            }
        }

        int smallRingAns = 0;
        int bigRingAns = 0;
        // 计算出最优的 小环解 和 大环解
        for (int i = 0; i < n; i++) {
            // 不是环里面的点 / 已经遍历过的点 直接跳过
            if(indegree[i] == 0) {
                continue;
            }

            // 是未遍历的环的节点
            int ringSize = 1; // 环的节点数 为了快速定位是大环还是小环
            indegree[i] = 0; // 入度置为0
            int cur = i;
            while(favorite[cur] != i) {
                cur = favorite[cur];
                indegree[cur] = 0;
                ringSize++;
            }

            // 小环(可以累加)
            if(ringSize == 2) {
               smallRingAns += 2 + deep[i] + deep[favorite[i]] ;
            }
            // 大环
            else {
                bigRingAns = Math.max(bigRingAns, ringSize);
            }


        }

        // 对比 大小环的解
        return Math.max(smallRingAns, bigRingAns);
    }
}
